package 我的Java学习_算法基础.day_07;

import java.util.HashSet;
import java.util.Set;

/**
 * @author 挚爱之夕
 * @date 2021/8/19 - 08 - 19 - 20:47
 * @Description: 我的暑假Java学习.day_06
 * @Version: 1.0
 */
public class _109_子集生成 {
    public static void main(String[] args) {
        int[] A ={1,2,3};
        Set<Set<Integer>> subsets = getSubsets1(A,A.length-1);
        System.out.println(subsets);
    }

    /**
     * 生成所有子集
     * @param A 集合
     * @param index A中最后一个元素下标
     * @return 所有子集，包括空集
     */
    private static Set<Set<Integer>> getSubsets(int[] A,int index){
        Set<Set<Integer>> newSet = new HashSet<>();
        if(index==0){//处理第一个元素
            Set<Integer> nul = new HashSet<>();//空集
            Set<Integer> first = new HashSet<>();
            first.add(A[0]);
            newSet.add(nul);
            newSet.add(first);
            return newSet;
        }
        Set<Set<Integer>> oldSet = getSubsets(A,index-1);
//        newSet.addAll(oldSet);//可用此句代替遍历时添加
        for(Set<Integer> set: oldSet){
            //对于每个集合，cur这个元素可以加进去，也可以不加进去
            newSet.add(set);//保留原样
            Set<Integer> clone = (Set<Integer>) ((HashSet)set).clone(); //集合采用引用，为保留原样，需要克隆
            clone.add(A[index]);
            newSet.add(clone);
        }
        return newSet;
    }

    /**
     *
     * 生成所有子集
     * @param A 集合
     * @param index A中最后一个元素下标
     * @return 所有子集，包括空集
     */
    private static Set<Set<Integer>> getSubsets1(int[] A,int index){
        Set<Set<Integer>> res = new HashSet<>();
        res.add(new HashSet<>());//初始化为空集
        //从第一个元素开始处理
        for (int i = 0; i <= index; i++) {
            Set<Set<Integer>> res_new = new HashSet<>();//新建一个大集合
//            res_new.addAll(res);//把原来集合中的每个子集都加入到新集合中
            //遍历之前的集合，全部克隆一遍
            for (Set e :
                    res) {
                res_new.add(e);//替代上式
                Set clone = (Set) ((HashSet) e).clone();
                clone.add(A[i]); //把当前元素加进去
                res_new.add(clone);//把克隆的子集加到大集合中
            }
            res = res_new;

        }
        return res;
    }
}
